package com.linskating.wheat.utils;

import java.util.List;

public class AlgebraUtil {

    // 相似度越高，相似度值越小
    public static int SimilarityCoefficient(List<String> tagsList1, List<String> tagsList2) {
        int n = tagsList1.size();
        int m = tagsList2.size();

        if (n * m == 0) return n + m;

        int[][] d = new int[n + 1][m + 1];

        for (int i = 0; i < n + 1; i++) d[i][0] = i;

        for (int j = 0; j < m + 1; j++) d[0][j] = j;

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = d[i - 1][j] + 1;
                int down = d[i][j - 1] + 1;
                int leftDown = d[i - 1][j - 1];
                if (!tagsList1.get(i - 1).equals(tagsList2.get(j - 1))) leftDown += 1;
                d[i][j] = Math.min(left, Math.min(down, leftDown));
            }
        }
        return d[n][m];
    }
}
